// 有向图的基本实现
// 这里依然采用了邻接表来表示
// 大部分代码可以复用无向图的实现，只不过这次的链接确认加入了方向考虑

import { NonDirectGraph } from './无向图'

export class DirectGraph<T = unknown> extends NonDirectGraph<T>{
    // 构造函数
    constructor(...initialVertexesList: T[]) {
        super();
        initialVertexesList.forEach((v) => {
            super.addVertex(v);
        });
    }
    get [Symbol.toStringTag]() {
        return 'DirectGraph';
    }
    // 重写连通分量方法：需要判断方向
    addConnection(vertex1: T, vertex2: T, V1ToV2: boolean = true): boolean {
        if (vertex1 === vertex2) {
            throw new RangeError('输入参数形成了自连通路，请检查输入');
        }
        // 首先需要保证两个顶点均在集合中
        if (!this.vertexes.includes(vertex1)) {
            this.warnVertexNotExist(vertex1);
            return false;
        }
        if (!this.vertexes.includes(vertex2)) {
            this.warnVertexNotExist(vertex2);
            return false;
        }
        // 确定方向
        if (!V1ToV2) {
            let temp = vertex1;
            vertex1 = vertex2;
            vertex2 = temp;
        }
        // 更新单方向连通分量
        this.adjList.get(vertex1)?.push(vertex2);
        return true;
    }
}



// 测试用例
const dg = new DirectGraph("A", "B", "C", "D", "E", "F", "G", "H", "I");
const dg2 = new DirectGraph();
console.log(dg.addConnection("A", "B"));
console.log(dg.addConnection("A", "C"));
console.log(dg.addConnection("A", "D", false));
console.log(dg.addConnection("C", "D"));
console.log(dg.addConnection("C", "G"));
console.log(dg.addConnection("D", "G"));
console.log(dg.addConnection("D", "H"));
console.log(dg.addConnection("B", "E"));
console.log(dg.addConnection("B", "F"));
console.log(dg.addConnection("E", "I"));
dg2.show();
dg.show();
dg.dfs('A');
console.log(dg.getMinDistance('A', 'G'));// 2
console.log(dg.getMinDistance('G', 'A'));// -1
console.log(dg.getMinDistance('E', 'I'));// 1
console.log(dg.getMinDistance('A', 'H'));// 3
console.log(Object.prototype.toString.call(dg));